|
In formal language theory, a context-free grammar ''G'' is said to be in Chomsky normal form (discovered by Noam Chomsky) if all of its production rules are of the form: : ''A'' → ''BC'', or : ''A'' → ''a'', or : ''S'' → ε, where ''A'', ''B'', and ''C'' are nonterminal symbols, ''a'' is a terminal symbol (a symbol that represents a constant value), ''S'' is the start symbol, and ε denotes the empty string. Also, neither ''B'' nor ''C'' may be the start symbol, and the third production rule can only appear if ε is in ''L''(''G''), namely, the language produced by the context-free grammar ''G''. Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form and has a size no larger than the square of the original grammar's size. ==Converting a grammar to Chomsky normal form== To convert a grammar to Chomsky normal form, a sequence of simple transformations is applied in a certain order; this is described in most textbooks on automata theory.〔〔 Section 7.1.5, p.272〕〔 Section 6.2 "Die Chomsky-Normalform für kontextfreie Grammatiken", p.149-152〕 The presentation here follows Hopcroft, Ullman (1979), but is adapted to use the transformation names from Lange, Leiß (2009).〔For example, Hopcroft, Ullman (1979) merged TERM and BIN into a single transformation.〕 Each of the following transformations establishes one of the properties required for Chomsky normal form. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chomsky normal form」の詳細全文を読む スポンサード リンク
|